% \documentclass{article}%article类型文章
\documentclass{ctexart}
\usepackage{ctex}%支持中文编译的宏包，编译一定要选择XeLatex啊！！
\usepackage[utf8]{inputenc}

\title{高等并行计算机体系结构}%标题
\author{毛豫新 BY2106104  张佳一 SY2106303 李晓宇ZY2106322 杜晨鸿BY2104502}%作者
\date{2022-01}%日期
 
%——————以下宏包功能不一定用上，请自行学习——————————
% \usepackage{natbib}
\usepackage[table,xcdraw]{xcolor}%提供更多的色彩
\usepackage{extarrows} %长等号扩展
\usepackage{booktabs}%三线表格
\usepackage{float}%浮动体宏包
\usepackage{amsmath}%扩充数学富符号
\usepackage{multirow}
% \usepackage{cite}
\newcommand{\upcite}[1]{\textsuperscript{\cite{#1}}}
%设定了引用命令\upcite来右上角引用
\usepackage{graphicx}%引入图片宏包
\usepackage{subfigure}%小图片
\usepackage{listings}  %代码块当然数学作业也用不到
\usepackage{makecell}

%——————————————————————————————————————————————————
\newcommand{\res}[1]{\mathrm{Res}\left[{}#1 \right]}
\newcommand{\ykh}[1]{\left({}#1\right)}%定义命令\ykh{}来输出圆括号，如果直接输出()会导致固定的括号大小与公式不匹配
\usepackage{geometry}%设定版面格式
\geometry{
  a4paper,
  top=25.4mm, bottom=25.4mm,
  headheight=2.17cm,
  headsep=4mm,
  footskip=8mm
}%设置标准页边距
\usepackage[justification=centering]{caption}%图片标题居中
%不熟悉latex的数学公式代码可以去www.latexlive.com 生成。
% 设置题注格式
\renewcommand {\thefigure} {\arabic{figure}}

\ctexset{secnumdepth=4,tocdepth=3}
\begin{document}%正文部分
\captionsetup{labelformat=default,labelsep=space}  % 去除题注冒号
\maketitle%显示正文之前的属性如作者
\tableofcontents%生成目录
\newpage%新的一页

\section{绪论}

本报告主要讲述片上多处理器的******(由毛豫新编写)。

本报告的内容如下:
\begin{enumerate}
  \item 第一节为绪论部分，主要讲解单片多处理器诞生的背景及本文结构,由毛豫新撰写\upcite{KunleNayfeh-51}；
  \item 第二节讲解片上多处理器(Single-Chip Multiprocessor)与单个超标量处理器的对比试验,由杜晨鸿撰写\upcite{KunleNayfeh-51}；
  \item 第三节讲解多标量处理器(Multiscalar Processors),由张佳一撰写\upcite{SohiBreach-52}；
  \item 第四节讲解片上多处理器对程序的优化思路，即将串行程序分成多个部分并行执行\upcite{KrishnanTorrellas-53}。
        \\(Speculative Multithreading),由李晓宇撰写。
\end{enumerate}



\section{单片多处理器}
\subsection{实验目的及主要内容}
为探究单片多处理器对处理器性能的影响，
Kunle\upcite{KunleNayfeh-51}等人设计了一个模拟试验，
以探究将一个超标量处理器分割为多个处理器后，
处理器的串行及并行性能的变化。

该论文利用\ref{SS-fig}所示的超标量处理器(6路超标量)
及\ref{MP-fig}所示的单片多处理器(四个2路超标量处理器)进行性能比较。
值得注意的是，
为了保证高效的指令级并行及乱序执行，
超标量的“reorder”占用了大量的面积（约30\%）。
这就导致单片多处理器四个核在一起还比单个超标量处理器要小一点点。
此外，单片多处理器的主频其实可以做得比单个超标量处理器更高，
但这里强制两种处理器具有相同的主频。
\begin{figure}
  \centering
  \includegraphics[height=150pt]{./SS-flat.png}
  \caption{超标量处理器平面图}
  \label{SS-fig}
\end{figure}

\begin{figure}
  \centering
  \includegraphics[height=150pt]{./MP-flat.png}
  \caption{单片多处理器平面图}
  \label{MP-fig}
\end{figure}

\subsection{仿真软件}
试验采用数值试验的方式进行，
所用软件为斯坦福大学开发的SimOS模拟器（现在已经下载不到了）；
基于MIPS指令集（龙芯LoongArch的前身）；
使用的操作系统是硅谷图形的lRIX 5.3操作系统。

为验证处理器的并行及串行性能，共采用了9个程序进行运行测试，
由于在当时，并行计算尚处于萌芽阶段，因此大部分程序是串行的，
需要进行一定程度的修改才能在单片多处理器上并行执行。
其中，compress、eqntott、m88ksim、MPsim为整数型程序，
compress是一个压缩程序，无法并行执行，故在两种处理器中都是串行执行的，
eqntott中存在一个占用90\%执行时间的大循环，在单片多处理器中将其改为循环级并行，
m88ksim使用SUIF编译器进行编译，以实现并行执行，
MPsim通过手动修改，将其编写为4个线程，运行在单片多处理器的四个核心中；
applu、apsi、swim、tomcatv为浮点数型程序(即基于浮点数运算的科学计算程序)，
它们采用与m88ksim相同的方法，利用SUIF编译器自动实现并行执行；
pmake是采用并行方式编写的cmake。

\subsection{仿真结果}
如\ref{MP-time}所示，为单片多线程中的一个核心执行程序的时间分解图；
如\ref{SS-time}所示，为超线程处理器程序的时间分解图。
可以看出，超线程IPC的提升并不明显。其原因如下：
\begin{enumerate}
  \item 超标量处理器的投机执行更多，错误的投机执行导致缓存污染，从而引发未命中；而已经发生未命中的流水线又会更容易发生新的未命中（后者主要引发L2未命中）。这就导致它有较高的未命中率。
  \item 虽然超标量处理器的分支预测率提高了些，但缓存命中率也出现了下降，而超标量处理器的缓存访问速度也比单片多处理器慢得多。
\end{enumerate}

此外，小核心的IPC主要损失在数据缓存读取上，这是因为它的L1缓存比较小；大核心上运行整数型程序的IPC主要损失在流水线上，这是因为程序的指令级并行度不够，而且L1缓存读取需要2个时钟；
大核心上浮点型程序的IPC主要损失在数据缓存上。

\begin{figure}
  \centering
  \includegraphics[height=150pt]{./SS-time.png}
  \caption{超标量处理器运行时间分解图}
  \label{SS-time}
\end{figure}

\begin{figure}
  \centering
  \includegraphics[height=150pt]{./MP-time.png}
  \caption{单片多处理器运行时间分解图}
  \label{MP-time}
\end{figure}

对于整个单片多处理器，其L2缓存未命中率并不比单个超线程处理器好，这是因为线程间存在大量的通讯。

如\ref{SS-MP-cmp}所示，为两种处理器运行速度的对比（以超标量处理器单核的的运行速度为1）。
可以看出， 对于无法并行执行的程序（如compress），单核的单片多处理器仍有有超标量处理器70\%的性能；
对于存在大量线程间通讯但又能实现细粒度多线程的代码，两种处理器的效率相近；
高并行度的代码使得单片多处理器可以运行粗粒度多线程，但超标量处理器由于指令窗的限制，
无法对下一个循环的代码进行细粒度并行，
所以就比单片多处理器慢（单片多处理器比超标量处理器强了约50-100\%）。

\begin{figure}
  \centering
  \includegraphics[height=150pt]{./SS-MP-cmp.png}
  \caption{单片多处理器(MP)与超标量处理器(SS)的性能对比}
  \label{SS-MP-cmp}
\end{figure}

\subsection{小结}

如\ref{intel12}所示，为12代intel处理器示意图。
时隔20余年，我们在当代处理器中见到了这篇论文中所示的“单片多处理器”及“超标量处理器的集合”。
由于采用了非对称架构，使得并行度高的程序(如科学计算)可以分配多个小核心并行执行；
临界区或者串行程序(如计算机游戏)可以分配给大核心运行，以获得整体最优的CPU性能。

\begin{figure}
  \centering
  \includegraphics[height=150pt]{./intel-i12.png}
  \caption{intel12代处理器}
  \label{intel12}
\end{figure}

\section{Multiscalar Processors}

\subsection{From Superscalar to Multiscalar}

介绍研究背景——超标量技术，并指明目前ILP的发展瓶颈（回答到底要解决什么问题），进而引出本文提出的新方法——多标量处理技术。

通过一个程序计数器不断进行“fetch-execute”操作的这种顺序执行的基本范例已经存在了50多年了。这种顺序范式的一个结果是，程序在编写时就默认了指令也将按照相同的顺序执行。

然而，为了实现更高的性能，现代处理器试图在一个周期内同时执行多条指令，即利用**指令级并行（ILP）**，**超标量**（Superscalar）技术就是在单个处理器内核中实现了指令级并行的一类处理器架构。超标量处理器会维护一个动态指令窗口（dynamic instruction window），同时它有一个指令调度器（dispatcher）来决定哪些指令能够并发处理，并把这些指令分派（dispatching）到不同的执行单元（或称为功能单元）中同时执行，这就实现了指令级的并行。

但也正因如此，在某些情况下指令实际执行的顺序与初始的指令顺序可能会有所不同，这称为**指令重排（reordering）**。为了确保程序能够正确执行（与顺序执行时的语义相一致），我们需要解决不同指令之间的**数据依赖（data dependences）**与**控制依赖（control dependences）**问题。尤其是控制依赖，它是实现程序的高度并行执行的一个主要障碍，主要表现在对**分支指令（branch instructions）**跳转条件的判断上。

为了解决控制依赖，一种方案是将静态程序表示为**控制流图（control flow graph，CFG）**，其中结点是基本块（basic block），边则表示了从一个基本块到另一个基本块的控制流信息。那么程序的动态执行则可以看作是以一种**投机（speculative）**的方式（例如分支预测）在CFG上流通，且程序的每次运行都会生成一个基本块的动态序列。

\begin{figure}
  \centering
  \includegraphics[height=150pt]{./assets/image-20211201204656882.png}
  \caption{null}
  \label{null}
\end{figure}

传统的顺序执行处理器是逐指令进行的。超标量处理器利用了指令级并行（ILP），在CFG中，一个基本块可以看作一个指令窗口，因此超标量处理器可看作是逐基本块执行的。

虽然现代微处理器架构通过**超标量技术**（superscalar）已经取得了很不错的表现，但其指令级并行（ILP）程度是有限的。因为超标量试图在一个时钟周期内取出多条指令并行执行，这是通过内置多条流水线来实现同时执行多个处理的，其实质是以空间换取时间。理论上来说，指令窗口越大（同时发出的指令越多），程序执行的并行度就会越高，但相应地，对不同指令之间的依赖关系检查（为了保证程序正确执行）的成本也将会大量增加。这个成本不仅包含为了实现依赖性检查而增加的逻辑门，还有在这些逻辑门之间的时间延迟。研究表明逻辑门成本在某些状况下可能会高达 $\displaystyle k^{2}\log n$ ，其中 $n$ 是处理器的指令集数量，而 $k$ 是同时发送的指令数量。由于这种平方级的时间复杂度，在现在的高时钟速度（短时钟周期）下难以设计出能够支持更大指令窗口和更宽发射的硬件结构，从而限制了超标量架构的整体性能。

因此，为了实现更高水平的并行度，**多标量（Multiscalar）**处理器对程序的执行进行了进一步的抽象——引入了**任务（task）**的概念，一个任务就是CFG的一部分（e.g. 一个基本块的一部分、一个基本块、多个基本块、一个单个循环迭代、一个整个循环、一个函数调用等）。每个任务会被分配给一个处理单元（processing unit），多个任务将在不同的**处理单元（processing unit）**中并行执行，这就使得在一个时钟周期（cycle）能够同时执行多条指令。

这个概念听起来似乎很简单，但是，为了确保程序的正确执行（保证顺序执行的语义），关键是要**正确地解决任务之间的数据依赖关系**，这就需要一系列的**软硬件支持**（support on software and hardware）来保证，也正是在任务间数据通信这个领域，多标量技术与传统方法有很大的不同与优势。

下面详细介绍了多标量处理器方法。第二节介绍了多标量处理器的一种可能架构以及所需要的软硬件支持，并举例介绍了多标量程序的威力。第三节分析了多标量执行模型的周期分布，并介绍了产生这些损失周期（lost cycles）的原因，以及应对措施。第四节从四个方面阐明多标量相较于超标量方法的优势。第五节对全文做了总结归纳。

\subsection{Multiscalar Architecture}

\subsubsection{Multiscalar Architecture}

详细介绍多标量处理器的架构。
\begin{figure}
  \centering
  \includegraphics[height=150pt]{./assets/image-20211201203828792.png}
  \caption{null}
  \label{null}
\end{figure}

多标量处理器的一种可能架构如图1所示。

一般来说，多标量处理器包括一个处理单元的集合，不同处理单元用单向环（unidirectional ring）连接起来，每个处理单元都有其内部的指令排序机制，且有一个排序器（sequencer）将任务分配给处理单元。一旦任务分配给处理单元，处理单元就会获取（fetch）该任务的指令并执行（execute），直至任务完成。

需要注意的是，任务虽然是不同的指令组，但任务之间并不是独立的。为了正确执行程序（获得程序顺序执行时的结果），研究人员采用了两种策略：

\begin{itemize}
  \item  首先，确保每个处理单元都遵循分配给它的任务顺序执行时的语义。
  \item  其次，对不同处理单元之间强制施加一个执行顺序，这是通过将处理单元组织成一个循环队列来实现的，队头指针和队尾指针分别指向了正在执行最早任务和最晚任务的处理单元。
\end{itemize}

除此之外，每个处理单元还有一个Data Bank来缓存数据和控制信息，以对投机执行的任务进行动态检查。

\subsubsection{Dependences on Registers and Memory}

如何解决寄存器和内存上的数据依赖问题？

在执行任务中的指令时，需要频繁地读变量和写变量，因而会产生和消耗**值（values）**，这些值被存放在寄存器（register）或者内存（memory）中。多标量执行时必须确保指令所消耗和产生的值与顺序执行中的值相同，换句话说，我们需要同步不同指令的数据依赖关系。

\textbf{Registers Dependences}

对于寄存器上的数据依赖，我们可以对寄存器上的值进行保留，使前序任务中写入寄存器的值与后继任务中对这些值的读取保持同步。具体来说，每个任务都有一个create mask来保存该任务产生的寄存器值，当任务产生寄存器值时，系统就会将对应的create mask沿着图1中的单向环转发到其逻辑后继单元中。对于一个后继任务来说，它所有前序任务所产生的寄存器值将会保存在accum mask中，即accum mask包含了所有前序任务的create mask。如果任务需要使用这些值，则消耗指令（consuming instruction）必须在接受到该值后才能继续执行，否则它将一直等待直到该值到达。

\textbf{Memory Dependences}

对于内存上的数据依赖，情况则稍有不同。如果已知任务消耗（通过load指令）了前继任务中产生（通过store指令）的内存值，则可以同步这个值的消耗和产生（或者说，读和写）。但不像寄存器值，在通常情况下，我们无法提前精确地确定一个任务消耗或产生了哪些内存值。此时，我们有两种策略来解决内存上的数据依赖问题。
\begin{itemize}
  \item 保守（conservative）的策略就是等待，直到load指令能够读到正确的值。这种策略通常意味着在一个任务中要推迟load指令，直到所有前序任务的store指令完成，但这样做最坏结果就是接近顺序执行。
  \item 激进（aggressive）的策略就是通过投机执行（或预测执行）load指令，即假定前序任务不会将值store在现在要读的同一个内存位置中，因而可以放心地继续执行load指令。这种策略要求在程序执行过程中进行动态检查，如果发现错误，即任务使用了不正确的数据，那么就回退该任务，且后继任务也需要回退。
\end{itemize}

多标量处理器采用激进的策略。具体来说，要增加一个硬件——**地址解析缓冲区（Address Resolution Buffer, ARB）**，来保存投机内存操作，检测内存依赖冲突，并启动纠正操作。ARB可以被视作活跃任务的投机内存操作（load指令）的集合，这些指令/操作产生的值保存在ARB中。除此之外，ARB还会追踪执行load和store位操作的处理单元，并通过检查这些位来确认是否存在内存依赖冲突，例如如果后继单元的load操作发生在前一个单元的store之前，则违反内存依赖原则。

由于投机执行的性质，我们必须保证任务可以正确执行，也可以从不正确的执行中恢复。如果控制投机，例如对下一个任务的预测不正确，则必须撤销后继任务，并恢复正确的任务序列。同样地，如果一个任务使用了不正确的数据值，也必须撤销该错误的任务，并恢复正确的数据值。在任何情况下，撤销任务的操作都会导致撤销所有后继任务，否则，维护顺序语义将会变得十分复杂。

\subsubsection{Multiscalar Program}

举例说明多标量程序的威力。

为了说明多标量执行模型的威力，我们考虑图3中的示例。

\begin{figure}
  \centering
  \includegraphics[height=150pt]{./assets/image-20211201230055109.png}
  \caption{null}
  \label{null}
\end{figure}

在这个代码段中，重复的从buffer数组中拿出一个符号（symbol），然后线性搜索链表中是否有和这个符号匹配的符号。如果有，那么就进行处理，如果不存在匹配的符号，就在链表中添加一个记录，表示这个符号。在初始化执行后，addlist操作将会变得很少，因为大部分符号已经和链表中的元素相匹配了。在多标量执行中，一个任务就是外层循环的一次迭代，即包括了在list中对特定符号的一个完整搜索。每个搜索都有一个特定的符号，不同任务并行地执行对链表的搜索，这样便能大大加快程序的执行速度。

在实际实现中，多标量处理器的排序器（sequencer）需要关于程序控制流的结构信息，特别是，它需要知道CFG中的哪些任务可能是任何给定任务的后继，以便快速遍历完CFG。幸运的是，这些信息可以在编译时就静态地确定，并保存在任务描述符（task descriptor）中，而任务描述符可以放置程序文本中，例如，在任务的代码之前。此外，程序中还会有一些转发位（forward bit）和停止位（stop bit）来标注，分别表示需要转发和任务停止。

为了协调不同任务之间的执行，需要根据任务可能消耗的值集和可能产生的值集来描述每个任务。正如2.2节所介绍的，处理寄存器值的过程很简单，编译器对CFG执行静态分析即可获得任务可能产生的寄存器值，并将其保存在create mask中，而create mask的位置很自然地也应该在任务描述符中。

\begin{figure}
  \centering
  \includegraphics[width=0.9\textwidth]{./assets/image-20211202134210359.png}
  \caption{null}
  \label{null}
\end{figure}

图4描述了图3代码在多标量执行时其中一个任务的执行过程，上面是任务描述符，右边则是forward bits和stop bits。代码注释如下：

create mask
\begin{itemize}
  \item \$20: index, 即外循环变量
  \item \$23: symbol，即本轮loop所要查询的symbol。
  \item \$17: list, 即内循环指针
  \item \$8: *list, 即list中的待匹配symbol。
  \item \$4: 传递参数的寄存器，每次在函数调用之前使用。
\end{itemize}

其他寄存器
\begin{itemize}
  \item \$21: listhd，链表头指针
  \item \$16: BUFSIZE
\end{itemize}

LABEL
\begin{itemize}
  \item OUTER：外循环开头
  \item INNER：内循环开头
  \item SKIPCALL：若list != NULL，则跳转到内循环的头INNER，继续向后遍历链表
  \item INNERFALLOUT：内循环结束，判断list
        \begin{itemize}
          \item 若list = NULL (\$17 = 0)，则说明遍历完成且没有找到匹配的符号，addlist(symbol)
          \item 若list != NULL (\$17 != 0)，则说明找到了匹配的符号且已经process()完了，直接跳过内循环 SKIPINNER。
        \end{itemize}
  \item SKIPINNER：比较index与BUFSIZE，判断是否要结束外循环
\end{itemize}

在本例中，一个task是外循环的一次迭代，且根据匹配结果的不同，有两个后继任务（successor）。这个任务会产生5个值（value）： \$4，\$8，\$17，\$20，\$23。其中，\$20，\$23 都有一个转发位标记，这是因为后继任务需要最新的循环变量index（\$20），而转发 \$23 是因为后继任务可能与当前任务所搜索的symbol是相同的，因而后继任务在addlist时就需要考虑前序任务是否已经进行了addlist，只是尚未收到更新，因而当前任务能够直接跳过addlist这一步以防止重复加入。需要注意的是，没有必要转发一个任务产生的所有值，而仅仅只需要考虑那些生存域超过了当前任务（live outside a task）的值，即那些在任务结束时不会被回收的值（are not *dead* at the end of a task）。在实际处理时， \$8 和 \$17 由于会在内层循环中反复更新，只需在最后一次更新后转发即可，因此在内层循环结束（INNERFALLOUT）时，可以直接释放（release）这两个寄存器。

\subsection{Distribution of Cycles in Multiscalar execution}

在本节，我们通过考虑多标量执行中处理单元的周期分布来对多标量模型有一个更加详细的了解。回想一下，我们的目标是让每个处理单元执行有用的计算，并让这些处理单元并行执行，进而实现在一个给定时钟周期内同时执行多条指令。在理想情况下，每个周期会执行同样多有用的（useful）计算，但在实际执行过程中，由于（1）无用计算，（2）无计算，（3）保持空闲等原因，导致出现损失周期（lost cycles）。需要注意的是，无计算周期是由于数据依赖问题需要等待值的到来，而空闲周期则是因为没有分配任务。下面将详细讨论这几个问题，并给出了一些解决方案。

\subsubsection{无用计算周期（non-useful computation cycles）}

无用周期表示那些将要被撤销（squashed）的任务，而任务需要回退的两个可能原因是使用了（1）不正确的值，或（2）不正确的预测。因为回退一个特定的任务意味着要同样回退所有后继任务，因而一次回退可能对多标量处理器有很大的影响。

为了减少回退的可能性，我们需要在无用周期开始前，通过（1）同步数据通信（ synchronizing data communication），或（2）提前决定（determine early）两个操作，这样就能避免回退任务。

\paragraph{Synchronization of Data Communication}~{}
\newline
寄存器值之间的通信可以通过寄存器文件机制（register file mechanism）来实现，而内存值之间的通信则必须显示地进行同步。如果后继任务在前序任务store操作完成之前，从同一内存位置load，则会发生memory order squash。然而，我们在实验中观察到，这样的squash中虽然确实有发生，却很少是由于更新内存位置而发生的。几乎所有的memory order squash都是由于全局标量（global scalars）和结构（structures）的更新而发生的，比如文件或缓冲区指针和计数器。（这些变量都有它们自己的内存地址，因此无法为其分配寄存器。）

幸运的是，访问静态全局变量是编译器要分析的最容易的内存访问之一，它比访问任意的堆位置要容易得多。一旦识别出（潜在的）违规访问，就可以同步对内存位置的访问，以确保冲突的load和store以正确的顺序进行。这种同步可以用很多不同的方式实现：
\begin{enumerate}
  \item 可以创建对寄存器的人工依赖（artificial dependence），以使内存通信与寄存器通信同步
  \item 让load指令延迟指定数量个周期，以减少其在store完成前发生的概率
  \item 使用显式地信号量同步机制（signal-await）
\end{enumerate}

需要注意的是，任何同步机制都可能创建任务间依赖（inter-task dependences）关系，正如我们在3.2将要看到的，这将可能导致无用计算周期。

\paragraph{Early Validation of Prediction}~{}
\newline
一个任务是否会因为错误的预测而被回退，通常在已知前序任务执行的结束位置后才能确认，而任务执行的结束点通常是任务的结束位（stop bit）。在这段时间内，后继任务中可能执行了许多无用计算周期。例如，在循环时，我们需要等待本次迭代的所有指令都执行完毕后，才能确认出后续的迭代都是无用计算，必须要被压缩。如果一次迭代由数百条指令组成，那么去确认是否应继续循环所需花费就可能代表了将会继续执行数百个无用计算周期。

为了尽量减少这些周期造成的损失，我们可以考虑**尽早验证预测（Early Validation of Prediction）**。因为如果在任务启动后不久执行一些计算，以确定下一个任务是否确实被正确预测，那么用于无用计算所花费的时间可能会显著减少。回到循环的例子，如果本次迭代开始执行后不久便确认是最后一次迭代，那么下一个处理单元将会直接把任务重定位到循环的退出点（loop exit）而不是继续执行另一个（无用）循环。

有几种方法可以实现尽早验证预测：

\begin{enumerate}
  \item 一种选择是在任务中引入显式的验证预测指令（validate prediction instructions ）。
  \item 另一个选择，专门针对循环，它不需要新的指令，而更改循环的结构（顺序），以便在循环一开始时就判断是否会跳出循环。
\end{enumerate}

\subsubsection{无计算周期（non computation cycles）}

在这些损失的循环周期中，有些可能是顺序代码中不可避免的固有特征，而另一些可能是多标量执行所需的任务区分和任务调度的副产品。

\paragraph{Intra-Task Dependences}~{}
\newline
无计算周期的一个明显来源是**同一任务**的指令之间的依赖关系。因为每个任务都像一个小型程序，而每个处理单元就像一个单处理器，因此任何可以减少单处理器中损失周期的技术都可以用来减少无计算周期的出现。这些技术包括（但不限于）代码调度、乱序执行和非阻塞缓存。

\paragraph{Inter-Task Dependences}~{}
\newline
在多标量执行中，无计算周期的一个更重要的来源是**不同任务**的指令之间的依赖关系。如果在并发执行的任务中，后继任务需要消耗前序任务产生的值时，那么消耗任务需要暂停等待生产任务。在这种情况下，可能会导致接近顺序的执行。

考虑图3中的例子。如果外循环的index在循环结束时被更新（通常情况下，编译成汇编代码就是这样的），那么外循环的所有迭代会被序列化，因为下一轮迭代需要更新后的index才能继续。另一方面，如果我们在任务的早期更新并转发index，并保留一份index的副本供本地任务使用，那么不同任务则可以并行执行。

\paragraph{Load Balancing}~{}
\newline
在多标量执行中，由于任务必须按顺序结束，因此如果任务没有达到适当的粒度和（大致）相同的动态指令窗口大小，则可能会出现损失周期。也就是说，完成短任务的处理单元在等待前序任务的执行时是不会执行计算的。因此，最小化由于负载平衡损失周期的一个关键因素是选择具有适当粒度的任务。这意味着，每个任务有一个最小的指令窗口的限制。特别是，一个任务应该可以自由地包含函数调用。（在我们的例子中，任务的适当粒度是一次外循环的迭代，其中包含一个函数调用。）



\subsection{Comparison of Multiscalar with Other Paradigms}
本节讨论了多标量方法相较于传统ILP处理器（超标量方法）的一些优势及不同。

\subsubsection{Comparison with Superscalar}

\textbf{Branch prediction Accuracy}

如果平均分支预测的准确率为90\%，那么超标量方法在投机执行五个分支后，第五个分支能够正确执行的可能性只有60%。（当平均准确率为85%时，这个可能只有不到45%。）而多标量处理器把指令序列划分成各个任务，尽管任务内部也可能包含分支，但sequencer只需要预测不同任务的分支即可。因此多标量处理器在预测分支数超过5个时，仍然可以有很高的概率遵循正确的动态指令路径。

\textbf{Large window size}

超标量方法要求同时检查指令窗口中所有待发射指令的状态，而在多标量实现中，只需要检查很少的指令发射状态（每个处理单元仅需一个），因此多标量处理器可以有很大的指令发射窗口。
\textbf{Issue Complexity}

正如前文提到，超标量实现的指令发射逻辑复杂度为 $n^2$ 级别的，在现在的高时钟速度（短时钟周期）下难以设计出能够支持更大指令窗口和更宽发射的硬件结构，从而限制了超标量架构的整体性能。而在多标量实现中，sequencer将任务分配给各个处理单元，每个处理单元独立发射指令，这就使得多标量指令发射逻辑的整体复杂度很低。

\textbf{Loads and Stores}

在传统的实现中，load和store被给定了序列号（或按原始顺序保存），并与其所要访问的内存地址一起维护在一个缓冲区（buffer）中。
\begin{itemize}
  \item  如果要发射load指令，则要检查缓冲区，以确保前面没有store指令访问了同一个内存地址。
  \item  如果要发射store指令，则要检查缓冲区，以确保前面没有store或load指令访问了同一个内存地址。
\end{itemize}

在多标量实现中，因为有硬件支持（ARB），从而可以独立发射load和store指令，并在执行过程中进行动态检查即可，而无需知道前续或后继任务中的load和store。

\subsubsection{Compraison with Multiprocessors}

下表展示了多处理器与多标量方法在投机执行、任务划分、任务间依赖同步、以及寄存器空间和内存空间等方面的不同。

\begin{figure}
  \centering
  \includegraphics[width=0.9\textwidth]{./assets/image-20211214000949778.png}
  \caption{null}
  \label{null}
\end{figure}

由表可知，多标量处理器与多处理器在很多方面都十分相似，两者都能调度大块的并行代码，多标量处理器更像是一个具有较低调度开销的多处理器。然而，它们仍有一个很大的不同。多处理器需要编译器将程序划分为任务，并且要保证任务之间的所有依赖关系都已知（或保守提供），多标量处理器则不需要这样的控制和数据独立的信息。显然，如果编译器可以将程序划分为保证独立的任务（例如循环的迭代），那么多标量处理器当然可以并行执行它们。多标量方法的优势恰恰就在于执行那些依赖性相对较低的任务，而这些信息往往不能被静态确认。



\subsection{Conclusion}

本文提出了多标量处理方法，一种利用细粒度指令级并行性的新范式，以及多标量程序的结构和多标量处理器的硬件架构，并将多标量处理器与其他ILP处理器（如超标量）进行了比较。多标量处理器在软硬件的支持下从顺序程序中最大程度地提取指令级并行。它通过将程序控制流图(CFG)划分为任务，这些任务被分配给一组处理单元，每个处理单元获取并以一种投机的方式执行其任务中的指令，从而实现指令级并行。

作者认为多标量处理器性能问题还不是很好，是由于他们的解决方法还有待于改进，未来会尝试不同的多标量架构进行实验。随着编译器等软件的改进，和更合理的硬件支持，多标量处理器能够更好的利用指令级并行，以至于超过其他的处理器范例。


\section{A Chip-Multiprocessor Architecture with Speculative Multithreading}
\subsection{片上多处理基本思想}
传统超标量机器随着指令窗口越来越大，实现成本平方级增加，并且因为指令之间的依赖，窗口的增大很难进一步挖掘指令并行性，加快程序运行速度。为了避免超标量架构所带来的限制，片上多处理器逐渐进入研究者的视野。片上多处理器通过将程序分成许多块（比如几十条指令作为一个程序块），让块与块之间在不同处理器上并行运行，从而反向利用局部性原理来寻找更多的指令并行性。这里每个程序块我们称之为线程，注意其同操作系统的线程含义不同。

\subsection{片上多处理器架构的实现关键}

片上多处理器架构的实现关键在于如何让多个程序块并行运行在不同处理器上，保证运行正确性的同时尽可能提升程序的运行效率。为此需要解决数据依赖和执行依赖。因为在逻辑上，划分的线程之间仍是串行的，即后面线程的执行仍然需要前面线程提供的信息。数据依赖指的是当前指令的执行需要前面线程提供相关数据。而执行依赖指的是当前线程是否执行取决于前面线程相关分支判断或者跳转指令的执行。这篇论文将线程的划分局限在循环中，所以暂不考虑执行依赖的问题，但是对应的框架仍能够很好地拓展到处理执行依赖的情况。而对于数据依赖的处理可以分为四个方面：
\begin{itemize}
  \item 如何识别数据依赖，包括基于寄存器和基于内存的数据依赖。
  \item 如何避免写读依赖，即前面线程不会读取到后面线程写入的值。
  \item 如何避免写写依赖，即后面线程写入的值会覆盖前面线程写入的值。
  \item 如何避免读写依赖，即后面线程能够正确读取到前面线程写入的值。
\end{itemize}

在上述三种数据依赖中，写读以及写写依赖其实是假的数据依赖，这是因为形成依赖的两条指令其实并不需要对方的数据，只是因为写入的地址相同而产生了数据依赖，而读写依赖则是真正的数据依赖。进一步相关框架的设计关键点可以总结为以下四点：
\begin{itemize}
  \item 设计相关软硬件方法在编译或者运行阶段去识别数据依赖。
  \item 设计存储系统，对私有存储和共享存储空间进行划分。存储空间大致可以划分为两种，第一种是每个处理器所私有的，对存储空间的拷贝，第二个是所有处理器或者部分处理器能够同时访问的。如何安排存储空间应该综合考虑实现成本和运行效率。
  \item 协调私有存储空间之间的通信，从而能够解决数据依赖。因为共享存储相关处理器都能访问，所以主要的通信应该集中于私有存储中。
  \item 设计指令调度策略来高效地执行程序。
\end{itemize}

\subsection{私有存储和共享存储的优缺点分析}
私有存储和共享存储的优缺点是相互对应的。具体可以总结为以下几点：
\begin{itemize}
  \item 私有存储能够让不同处理器并行执行访存，这是因为私有存储是多个存储设备，而共享存储一次只能执行一个访存操作，所以可能会导致两个没有依赖的访存操作阻塞。
  \item 私有存储能够解除写读和写写数据依赖，因为这两种数据依赖是因为存储位置相同而产生的依赖，私有存储中每个处理器都有一个该地址的存储位置，这样就能避免该数据依赖，这是共享存储做不到的。
  \item 共享存储占用存储空间小，成本低，因为它不需要像私有存储那样提供存储空间的多个拷贝。
  \item 共享存储不需要显示的通信，相比私有存储节省了通信成本，从而在特定场合能够提高运行效率。
\end{itemize}

\subsection{寄存器相关设计}
寄存器的地址是固定的，所以可以在编译期识别出数据依赖，从而知道不同线程之间哪两条指令是数据依赖的，并且寄存器容量小且成本低，所以共享存储的优点难以发挥，因此本架构中给每个处理器都分配有私有的寄存器组，从而尽可能提高运行效率。对应的架构只需要在指令调度时保证读写依赖即可，其它情况都可以乱序执行。私有寄存器组之间通过一个叫做SS Bus的总线传递数据，带宽为每个时钟周期1个字，且每个处理器只有一个读和写端口，并且传递数据的时钟周期数跟物理距离成正比，1到3个时钟周期。之所以这么设计是因为考虑到寄存器之间的通信较少，所以尽可能减少用于通信的硬件成本。具体架构可见下图。
\begin{figure}
  \centering
  \includegraphics[width=0.9\textwidth]{./image-20211222000642950.png}
  \caption{image-20211222000642950}
  \label{image-20211222000642950}
\end{figure}

接下来需要处理如何识别寄存器的数据依赖。因为只要关注读写依赖，所以关键在于确定每个写操作的生效范围，即对于一个读操作，架构需要知道它的数据来源是对应哪个写操作的。首先假定片上的处理器有无数个，从而所有的线程都能同时运行。当一个线程需要读数据时，有两种可能，一种是它之前写过该寄存器，那么只要直接读取私有寄存器上的数据即可，另一种是之前没有写过，那就需要找到它前面最后一个写入该寄存器的线程，让它来提供数据。所以架构首先对于每个线程，维护一个V比特，表示该线程是否拥有该寄存器的正确值，即能否直接读取其私有寄存器里的值。只要该线程之前写过该寄存器以及这个线程之前就已经收到了其它线程的值，其都能直接读取该寄存器的值，从而只要这两个操作发生时，硬件就将对应的V比特置为1。

当V比特为0时，架构就需要去寻找前面最后一个更新该寄存器的线程，这是可以在编译阶段知道的，即只需要判断该线程里面是否包含有该寄存器的写指令就行了。所以在预处理编译阶段识别，并在运行时使用F比特来标识该线程是否可能会对寄存器进行更新。因此最后一个更新该寄存器的线程即是最近的对应F比特为1的线程，向其申请值就行了。但是考虑到线程是并行执行的，所以写线程可能还没有执行到最后一次更新寄存器的指令处，这种情况读线程需要等待，为此硬件提供一个S比特来判断是否到达最后一次更新。同时这里有一个例外，即写线程是否会更新寄存器的值也取决于运行时状态，即分支指令的执行情况，所以可能写线程也没有寄存器的正确值，因此为了方便，硬件架构在每个写线程后面增加了release指令强制读取寄存器的值，从而保证其拥有正确的值，因此S比特的更新必须等到写线程执行完release指令。具体例子可见下图。
\begin{figure}
  \centering
  \includegraphics[height=150pt]{./image-20211222095120169.png}
  \caption{image-20211222095120169}
  \label{image-20211222095120169}
\end{figure}

寄存器数据传输的发起方式分为生产者发起和消费者发起。生产者发起即生产者最后一次更新寄存器后就将其主动写到总线上，供后续需要的线程读取。而消费者发起则是后续线程需要值时查找对应的生产线程，向其请求对应的值。生产者发起的模式是必须要实现的，因为后续线程请求值时前面线程可能还没有完成更新，所以需要阻塞等待，那就必须要前面线程更新完后主动通告其解除等待状态才行。而消费者发起的模式也需要实现，这跟处理器的数量有限有关。

前面一切的分析是建立在处理器数量无限，所有线程可以并行执行的基础上的。但是实际上处理器肯定是有限的，在这篇论文中，选定为4。这就会导致有读写数据依赖的两个线程可能不会同时在片上执行，这样读线程就无法从对应写线程申请获取值。第二个问题是读线程开始执行时，写线程可能已经更新完寄存器的值，并且使用生产者发起的模式传递了值，这样读线程是没有收到该值的，所以必须要显式执行消费者发起的模式来获取值。第一个问题解决也很简单，让当前片上的逻辑上第一个线程的寄存器值维护为串行语义即可，即其值跟串行执行是一致的，也就是把前面线程的值全部综合在一起。做到这点只需要维护一个X比特，来判断将要执行结束的线程是否都将其寄存器的值传给后续线程。这样片上第一个线程的寄存器值始终跟串行保持一致，当后续读线程索取数据时发现写线程已经执行完毕时，可以直接请求第一个线程。

\subsection{内存相关设计}

​内存与寄存器之间的区别在于以下几点：

\begin{itemize}
  \item 内存存储大小远远大于寄存器，每个处理器都有一份内存拷贝成本过高。
  \item 线程间内存可能存在大量数据交换，导致私有存储过高的通信开销，这是因为通常来说内存中值的生命周期远远大于寄存器值的生命周期。
  \item 内存的数据依赖是无法在编译期间可知的，所以必须要提供硬件来负责运行时的数据依赖检测。并且在前面线程还未执行完时，并不能确定其是否还会对某个特定内存地址进行更新，这就导致后续线程所有内存读操作都必须阻塞等待，从而严重损耗了运行效率。
\end{itemize}

​综上所述私有存储的几个优点无法发挥，所以必须采用一个大的共享存储来作为所有处理器的内存。为了能够仍然享受到私有存储的优点，采用私有存储和共享存储混合的存储架构，即L1 Cache作为私有存储，只要线程读写的数据量不超过L1 Cache的容量，那么还是可以避免写读依赖和写写依赖。指令调度方面，该架构采用投机执行，即不等待前面线程执行完毕就读取内存的值继续运行，通过硬件记录访存信息，判断一旦有违反数据依赖的操作后，重新执行该线程即可。最后系统需要第一个线程维持串行语义，规定其能直接更新共享内存，从而保持串行语义，而后续线程无法更新共享内存，即它们的L1 Cache上的数据是不能被替换的，如果要替换线程必须阻塞等待，但是它们可以读取内存中的值，从而允许投机执行。具体的投机执行线程示意图可见下图。
\begin{figure}
  \centering
  \includegraphics[height=150pt]{./image-20211222095153588.png}
  \caption{image-20211222095153588}
  \label{image-20211222095153588}
\end{figure}

​接着架构设计的关键在于如何搜集访存信息。这篇论文主要是使用MDT表来记录相关信息。表中每一行对应Cache中的一行，记录其内存地址，然后记录每个字都被哪个处理器读过或者写过，分别对应L和S比特位。这样通过LS比特位就能很轻易地判断要从哪个线程的L1 Cache中读取数据以及有没有违反数据依赖的情况发生。同时也需要定期清除表中无用的项，以让新的表项能够添加进来。当一个表项的所有LS比特位都为0时，就能够安全地删除它。只有非投机线程的L标志位全部为0，且非投机线程的私有Cache写到共享内存后，其S标志位也可以清零。MDT表中信息如下图所示。

\begin{figure}
  \centering
  \includegraphics[width=0.9\textwidth]{./image-20211222095238090.png}
  \caption{image-20211222095238090}
  \label{image-20211222095238090}
\end{figure}

​通过上述设计，架构已经能够允许正常执行内存的访存操作了，因此最后着重于如何进一步优化私有存储空间的执行效率。主要策略包括以下几个：

\begin{itemize}
  \item 对于非投机线程的L1 Cache采用写穿的策略，即它一旦要写数据，内存的相关位置也需要更新，这样可以尽可能避免其它线程读到错误的值。而其它线程只能采用写回的策略，并且一旦写过的Cache数据行要替换时，线程必须阻塞，这是因为投机执行导致线程写的值未必是正确的。
  \item 使用SW和SR标志位来尽可能减少读写操作通知MRT表的数量。因为MRT表主要关注的还是读写数据依赖，因此连续的读和连续的写操作只要记录一次就行了。当一个线程在私有存储读过一个数据后，硬件将对应Cache行的SR标志位置为1，并且通知一次MRT表，之后线程可以不通知就直接读。写数据同理，但是在当后续线程读过相同地址的数据后，SW标志位需要置零。之后SW标志位再次变为1就说明违反了读写依赖，因为前面线程在后面线程读过后再次更新了。
  \item 尽可能复用Cache中的数据。复用包括两个方面，第一个是线程重启，线程重启是因为违反了读写数据依赖，所以只需淘汰掉那些前面线程又重新写过的Cache行，用F比特位表示。第二个是线程结束执行后，开始运行下一个线程。此时还是要淘汰掉前面线程所写过的Cache行。但是不同的是这里前面线程是相对于即将开始运行的新线程来说的，因此对于执行结束的这个线程来说其实是它的后继线程，架构用FD比特来记录后继线程是否写过相关Cache行，当线程结束时，舍去FD比特为1的Cache数据即可。
\end{itemize}

最后Cache行的标志位如下所示：
\begin{figure}
  \centering
  \includegraphics[width=0.9\textwidth]{./image-20211222092944386.png}
  \caption{image-20211222092944386}
  \label{image-20211222092944386}
\end{figure}

\subsection{架构复杂度分析}

每个寄存器需要额外3n比特存储标志位，其中n是片上处理器的数量。每个寄存器中F和S标志位各占n比特，而V标志位仅需要1比特，X标志位需要n-1比特。当处理器数量为4时，总共需要12比特的存储空间，若寄存器原先有64比特，则总共增加约19%的存储空间。

MDT表中能够存放16K个访存操作，其可以设计放置到片上，也可以放置在L2 Cache处。具体MDT表的性能参数可见下表。

\begin{figure}
  \centering
  \includegraphics[height=150pt]{./image-20211222095035318.png}
  \caption{image-20211222095035318}
  \label{image-20211222095035318}
\end{figure}

每个Cache行相比原来增加了4个比特位，分别为SR、SW、F和FD比特位。

\subsection{架构性能测试}

​性能测试主要与传统4发射多标量处理器和12发射多标量处理器进行对比，而片上多处理器采用4核的结构，每个处理器都是4发射的多标量处理器，并且假定所有机器的时钟周期一样。具体的性能参数可见下表。

\begin{figure}
  \centering
  \includegraphics[height=150pt]{./image-20211222095314886.png}
  \caption{image-20211222095314886.png}
  \label{null}
\end{figure}

​通过仿真平台对常用的测试程序进行评估。具体结果可见下图，其中compress、ijpeg、mpeg以及eqntott是整数应用，而swim、tomcatv、hydro2d和su2cor是浮点数应用。可以看到在浮点数应用中，片上多处理器的性能远超传统的多标量处理器，在整数应用中，其略微超过12发射的多标量处理器。考虑到片上多处理器的时钟周期比12发射的多标量处理器大约少25%，即使在整数应用上，实际的加速效果也是可观的。

\begin{figure}
  \centering
  \includegraphics[height=150pt]{./image-20211222095631992.png}
  \caption{image-20211222095631992.png}
  \label{null}
\end{figure}

​同时片上多处理器运行不同程序时不同处理器的负载占比如下图所示。可以观察到由于整数应用的数据依赖较多，导致大部分指令运行集中在前面几个处理器上，使得最终的加速效果相比多处理器没有太大提升。但是对于浮点数应用，由于数据依赖较少，能够充分利用四个处理器，从而使得程序运行效率得到了优化。

\begin{figure}
  \centering
  \includegraphics[height=150pt]{./image-20211222100556342.png}
  \caption{image-20211222100556342.png}
  \label{null}
\end{figure}

​最后通过消融实验来验证系统参数对于性能的影响，从而验证架构设计的合理性。首先是关于SS Bus的时延和带宽。从下图中可以看到，提高带宽和减少时延对于程序执行性能的影响较少，因此架构为了成本将其带宽设为每时钟周期一个字，时延设为最大3个时钟周期，取决于具体处理器之间的物理距离。

\begin{figure}
  \centering
  \includegraphics[height=150pt]{./image-20211222101042610.png}
  \caption{image-20211222101042610.png}
  \label{null}
\end{figure}

\begin{figure}
  \centering
  \includegraphics[height=150pt]{./image-20211222101025880.png}
  \caption{image-20211222101025880.png}
  \label{null}
\end{figure}

​接着验证MDT相关参数对于性能的影响。如下图所示，L1 Cache到MDT表的时延对于程序运行效率的影响较少，因此最后设为2个时钟周期。而MDT表中能够存放的元素数量大大影响了程序的执行效率。但是可以观察到当元素数量增加到最大1K时，其对于程序执行效率的影响逐渐消失，这里架构为了保险仍将元素最大数量设为16K。

\begin{figure}
  \centering
  \includegraphics[height=150pt]{./image-20211222101147058.png}
  \caption{image-20211222101147058.png}
  \label{null}
\end{figure}

\begin{figure}
  \centering
  \includegraphics[height=150pt]{./image-20211222101407137.png}
  \caption{image-20211222101407137.png}
  \label{null}
\end{figure}

综上所述，片上多处理器是一种能够充分利用日益增长的晶体管数量的架构，是一种很有前途的设计方法，它是运行新一代多线程应用程序以及多工作负载的理想平台。此外，当提供了对投机执行的硬件支持时，它还可以处理串行的程序。这篇论文提出了一个足够通用的片上多处理器架构，它具有合适的硬件支持，可以以最经济有效的方式执行已经编译好的二进制文件。该文讨论了如何从二进制文件中提取线程，并提供了通过寄存器和内存实现通信的硬件支持。评估表明，这种体系结构为硬件需求适中的二进制文件提供了高性能执行。




\bibliographystyle{gbt7714-2005}
\bibliography{ref}

\end{document}